package com.wish.datastructure;

/**
 * Created by suliucheng on 2021/4/7 7:57
 * Directions: 构造单向环形链表也可以采用：将节类聚合到链表类，通过构造器注入第一个节点（在add中作为头结点），通过add增加节点
 * 设编号为 1,2,3...n的n个人围坐一圈，约定编号为k（1<= k<=n）的人
 * 从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那
 * 个人又出列，以此类推，直到所有人出位置，由此产生一个出队编号的序列。
 */
public class JosephuQuestion {
    public static void main(String[] args) {
        SitCircle circle = new SitCircle();
        circle.add(new Kid(1, "中国"));
        circle.add(new Kid(2, "美国"));
        circle.add(new Kid(3, "德国"));
        circle.add(new Kid(4, "澳大利亚"));
        circle.add(new Kid(5, "英国"));
        circle.add(new Kid(6, "日本"));
        circle.add(new Kid(7, "新西兰"));
        circle.add(new Kid(8, "希腊"));
        circle.add(new Kid(9, "伊朗"));
        circle.add(new Kid(10, "巴拿马"));
        circle.returnACircleLinkedList();
        int i = circle.readOut(3);
    }
}

/**
 * 若干个孩子坐在一圈
 */
class SitCircle {
    /**
     * 虚拟的头结点，不在循环中，但是该节点指向的第一个节点是第一个进入该循环链表
     */
    private Kid head = new Kid(0, "NoOne");
    /**
     * 现在共有 m 个孩子坐在一起，从编号为1 （n==1）的孩子开始报数，每次报到 3 （read==3）则出队列，求最后一个留在队列的孩子的编号
     *
     * 假设有两个虚拟指针 helper 指向最后一个进入圈内的小孩 first指向第一个进入圈子的小孩
     * 当小孩子开始数数的时候，就将 helper和first移动 read-1 次
     * 移动结束后 first指向的小孩就是出圈的小孩
     * 使用
     * first= first.next;
     * helper.next = first;
     */
    /**
     * 报数出圈
     *
     * @param read 每次报到 3 （read==3）则出队列
     * @return 最后一个留在队列的孩子的编号
     */
    public int readOut(int read) {
        Kid first = head.next;
        Kid helper = first;
        while (true) {
            if (helper.next == first) {
                break;
            }
            helper = helper.next;
        }
        while (true) {
            if (first == helper) {
                break;
            }
            for (int i = 0; i < (read - 1); i++) {
                first = first.next;
                helper = helper.next;
            }
            System.out.println("编号为：" + first.number + "的小孩：" + first.name + "出圈。");
            first = first.next;
            helper.next = first;
        }
        System.out.println("编号为：" + first.number + "的小孩：" + first.name + "留在最后。");
        return first.number;
    }

    /**
     * 调用此方法 得到闭环单向循环链表
     */
    public void returnACircleLinkedList() {
        Kid temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = head.next;
    }

    /**
     * 单向链循环表遍历查看
     */
    public void show(int times) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        Kid temp = head;
        int count = 0;
        while (true) {
            if (count == times) {
                break;
            }
            temp = temp.next;
            System.out.println(temp);
            count++;
        }
    }

    /**
     * 单向链表遍历查看
     */
    public void show() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        Kid temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
            System.out.println(temp);
        }
    }

    /**
     * @param kid
     */
    public void add(Kid kid) {
        Kid temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        temp.next = kid;
    }
}

/**
 * 孩子类
 */
class Kid {
    int number;
    String name;
    Kid next;

    public Kid(int number, String name) {
        this.number = number;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Kid{" +
                "编号=" + number +
                ", 姓名='" + name + '\'' +
                '}';
    }
}